# hybrid_algorithm.py
import numpy as np
import random
import math
from common import get_cost
from collections import deque
class StrategyScheduler:
    def __init__(self, n, distmat):
        self.strategies = {
            'SA': self._sa_step,
            'SA_GA': self._sa_ga_step,
            'SA_ACO': self._sa_aco_step,
            'SA_TS': self._sa_ts_step,
            'SA_VNS': self._sa_vns_step,
            'GRASP': self._grasp_step
        }
        self.strategy_weights = {name: 1.0 for name in self.strategies}
        self.strategy_scores = {name: 0 for name in self.strategies}
        self.last_improvement = {name: 0 for name in self.strategies}
    
    def update_scores(self, strategy, improvement):
        """根据策略表现更新评分"""
        if improvement > 0:
            self.strategy_scores[strategy] += 2
        elif improvement < 0:
            self.strategy_scores[strategy] -= 1
        else:
            self.strategy_scores[strategy] += 0.5
        
        # 衰减旧分数
        for s in self.strategy_scores:
            self.strategy_scores[s] *= 0.95
    
    def select_strategy(self, temp):
        """根据当前状态选择策略"""
        # 高温阶段优先全局搜索策略
        if temp > 1000:
            candidates = ['GRASP', 'SA_ACO', 'SA_GA']
        # 中温阶段平衡策略
        elif temp > 100:
            candidates = list(self.strategies.keys())
        # 低温阶段优先局部搜索
        else:
            candidates = ['SA_VNS', 'SA_TS', 'SA']
        
        # 根据分数选择
        candidate_scores = {s: self.strategy_scores[s] for s in candidates}
        total_score = sum(candidate_scores.values())
        if total_score == 0:
            return random.choice(candidates)
        
        rand_val = random.uniform(0, total_score)
        cumulative = 0
        for strategy, score in candidate_scores.items():
            cumulative += score
            if rand_val <= cumulative:
                return strategy
    def adjust_strategy_based_on_convergence(self, improvement_rate):
        """根据收敛速度动态调整策略权重"""
        if improvement_rate > 0.1:  # 快速改进阶段
            self.strategy_weights['SA_VNS'] *= 1.2
            self.strategy_weights['SA_TS'] *= 1.1
        elif improvement_rate < 0.01:  # 停滞阶段
            self.strategy_weights['SA_GA'] *= 1.3
            self.strategy_weights['SA_ACO'] *= 1.2
            
        # 归一化权重
        total = sum(self.strategy_weights.values())
        for key in self.strategy_weights:
            self.strategy_weights[key] /= total
class HybridAlgorithm:
    def __init__(self, algorithm_type, n, distmat, params):
        self.algorithm_type = algorithm_type
        self.n = n
        self.distmat = distmat
        self.params = params

        # 优化：使用 deque 作为禁忌表，提高插入/删除效率
        self.tabu_list = deque(maxlen=20)
        self.tabu_tenure = 20

        # 优化：预计算距离矩阵的倒数，避免重复计算
        self.inv_distmat = np.zeros_like(distmat)
        np.divide(1, distmat, out=self.inv_distmat, where=distmat!=0)
        
        # ACO 专用：初始化信息素矩阵
        self.pheromone = np.ones((n, n)) * 0.1
        self.pheromone_decay = 0.95
        self.pheromone_influence = 0.3

        # 优化：缓存邻域操作结果
        self.neighborhood_cache = {}
        self.iteration_count = 0
    def _sa_ensemble_step(self, sol, cost, temp):
        """集成多种策略的混合步骤"""
        strategies = [
            self._sa_step,
            self._sa_ga_step,
            self._sa_aco_step,
            self._sa_ts_step,
            self._sa_vns_step
        ]
        
        # 基于温度选择策略
        strategy_idx = min(int(temp / 50), len(strategies) - 1)
        selected_strategy = strategies[strategy_idx]
        
        return selected_strategy(sol, cost, temp)
    # 在HybridAlgorithm类中添加
    def adapt_hybrid_ratio(self, improvement_rate):
        """根据改进率动态调整混合比例"""
        if improvement_rate > 0.05:  # 快速改进阶段
            self.params['hybrid_ratio'] = max(0.3, self.params['hybrid_ratio'] * 0.9)
        else:  # 停滞阶段
            self.params['hybrid_ratio'] = min(0.9, self.params['hybrid_ratio'] * 1.1)
    def run_iteration(self, current_solution, temperature):
        current_cost = get_cost(self.n, self.distmat, current_solution)
        
        # 优化：根据温度调整混合策略比例
        hybrid_ratio = self.params.get('hybrid_ratio', 0.7)
        if temperature < 10:
            hybrid_ratio = max(0.3, hybrid_ratio * 0.8)
        if self.algorithm_type == "SA_ENSEMBLE":
            return self._sa_ensemble_step(current_solution, current_cost, temperature)
        if self.algorithm_type == "SA_GA":
            return self._sa_ga_step(current_solution, current_cost, temperature, hybrid_ratio)
        elif self.algorithm_type == "SA_ACO":
            return self._sa_aco_step(current_solution, current_cost, temperature, hybrid_ratio)
        elif self.algorithm_type == "SA_TS":
            return self._sa_ts_step(current_solution, current_cost, temperature, hybrid_ratio)
        elif self.algorithm_type == "SA_VNS":
            return self._sa_vns_step(current_solution, current_cost, temperature, hybrid_ratio)
        else:
            return self._sa_step(current_solution, current_cost, temperature)
        
    def _sa_step(self, sol, cost, temp):
        n = self.n
        best_candidate = sol
        best_candidate_cost = cost

        # 优化：减少不必要的复制
        for _ in range(5):
            op_type = random.randint(0, 2)
            i = random.randint(0, n-1)
            j = random.randint(0, n-1)
            if i > j:
                i, j = j, i
            if i == j:
                j = (j + 1) % n
            
            # 优化：使用缓存获取候选解
            key = (op_type, i, j)
            if key in self.neighborhood_cache:
                candidate, candidate_cost = self.neighborhood_cache[key]
            else:
                candidate = self._apply_operation(sol, op_type, i, j)
                candidate_cost = get_cost(self.n, self.distmat, candidate)
                self.neighborhood_cache[key] = (candidate, candidate_cost)
            
            if candidate_cost < best_candidate_cost:
                best_candidate = candidate
                best_candidate_cost = candidate_cost

        # 优化：避免重复计算 delta
        delta = best_candidate_cost - cost
        if delta < 0 or random.random() < math.exp(-delta / max(temp, 1e-8)):
            return best_candidate, best_candidate_cost
        return sol, cost

    def _apply_operation(self, sol, op_type, i, j):
        """应用操作并返回新解，避免不必要的复制"""
        n = self.n
        if op_type == 0:  # 交换
            new_sol = sol.copy()
            new_sol[i], new_sol[j] = new_sol[j], new_sol[i]
            return new_sol
        elif op_type == 1:  # 2-opt翻转
            new_sol = sol.copy()
            a, b = i, j
            while a < b:
                new_sol[a], new_sol[b] = new_sol[b], new_sol[a]
                a += 1
                b -= 1
            return new_sol
        else:  # 插入
            new_sol = sol.copy()
            temp_val = new_sol[j]
            # 优化：使用切片操作代替循环
            if i < j:
                new_sol[i+1:j+1] = new_sol[i:j]
                new_sol[i] = temp_val
            else:
                new_sol[j+1:i+1] = new_sol[j:i]
                new_sol[i] = temp_val
            return new_sol

    def _sa_ga_step(self, sol, cost, temp, hybrid_ratio=0.7):
        population = self.params.get('population', [])
        population_size = len(population)

        if random.random() < hybrid_ratio:
            return self._sa_step(sol, cost, temp)
        elif population_size >= 1:
            partner_idx = random.randint(0, population_size-1)
            partner_sol = population[partner_idx]
            
            # 优化：减少交叉操作的内存分配
            new_sol = self._ox_crossover_fast(sol, partner_sol)
            new_cost = get_cost(self.n, self.distmat, new_sol)
            
            delta = new_cost - cost
            if delta < 0 or random.random() < math.exp(-delta / max(temp, 1e-8)):
                return new_sol, new_cost
        return sol, cost

    def _ox_crossover_fast(self, parent1, parent2):
        """优化的顺序交叉算法"""
        n = self.n
        start, end = sorted(random.sample(range(n), 2))
        child = [-1] * n
        
        # 使用布尔数组标记已存在城市
        present = [False] * n
        child[start:end] = parent1[start:end]
        for city in child[start:end]:
            present[city] = True
        
        # 直接填充剩余位置
        pos = 0
        for city in parent2:
            if not present[city]:
                while pos < n and child[pos] != -1:
                    pos += 1
                if pos < n:
                    child[pos] = city
        return child

    def _sa_aco_step(self, sol, cost, temp, hybrid_ratio=0.8):
        if random.random() < hybrid_ratio:
            return self._sa_step(sol, cost, temp)
        else:
            # 优化：使用更高效的路径选择算法
            new_sol = self._aco_path_selection_fast(sol)
            new_cost = get_cost(self.n, self.distmat, new_sol)
            
            # 优化：只更新相关边的信息素
            self._update_pheromone_selective(sol, cost)
            
            delta = new_cost - cost
            if delta < 0 or random.random() < math.exp(-delta / max(temp, 1e-8)):
                return new_sol, new_cost
            return sol, cost
    
    def _aco_path_selection_fast(self, sol):
        """优化的ACO路径选择算法"""
        n = self.n
        start_idx = random.randint(0, n-1)
        length = random.randint(3, min(10, n // 2))
        end_idx = (start_idx + length) % n
        
        # 提取路径段
        if start_idx <= end_idx:
            segment = sol[start_idx:end_idx+1]
        else:
            segment = sol[start_idx:] + sol[:end_idx+1]
        
        # 优化：使用累积概率分布
        current_city = segment[0]
        remaining = segment[1:]
        new_segment = [current_city]
        
        while remaining:
            # 预计算所有概率
            probs = np.zeros(len(remaining))
            for idx, city in enumerate(remaining):
                pheromone_val = self.pheromone[current_city][city]
                # 使用预计算的距离倒数
                prob = pheromone_val * self.inv_distmat[current_city][city]
                probs[idx] = prob ** self.pheromone_influence
            
            total = np.sum(probs)
            if total <= 1e-6:
                next_idx = random.randint(0, len(remaining)-1)
            else:
                probs /= total
                next_idx = np.random.choice(len(remaining), p=probs)
            
            next_city = remaining.pop(next_idx)
            new_segment.append(next_city)
            current_city = next_city
        
        # 更新解
        new_sol = sol.copy()
        if start_idx <= end_idx:
            new_sol[start_idx:end_idx+1] = new_segment
        else:
            new_sol[start_idx:] = new_segment[:n-start_idx]
            new_sol[:end_idx+1] = new_segment[n-start_idx:]
        
        return new_sol

    # 在_sa_aco_step方法中
    def _update_pheromone_selective(self, sol, cost):
        """只更新相关边 + 精英增强"""
        n = self.n
        deposit_amount = 1000.0 / cost if cost > 0 else 1.0
        
        # 精英解额外增强
        elite_deposit = 5.0 * deposit_amount if cost < self.params.get('best_cost', float('inf')) else deposit_amount
        
        # 蒸发整个矩阵
        self.pheromone *= self.pheromone_decay
        
        # 只沉积当前解的边
        for i in range(n):
            a = sol[i]
            b = sol[(i + 1) % n]
            self.pheromone[a][b] += elite_deposit
            self.pheromone[b][a] += elite_deposit

    def _sa_ts_step(self, sol, cost, temp, hybrid_ratio=0.9):
        self._update_tabu_list()
        
        if random.random() < (1 - hybrid_ratio):
            candidate_sols = []
            candidate_costs = []
            
            # 优化：批量生成候选解
            for _ in range(5):
                move_type = random.randint(0, 2)
                i = random.randint(0, self.n-1)
                j = random.randint(0, self.n-1)
                if i > j:
                    i, j = j, i
                if i == j:
                    j = (j + 1) % self.n
                
                key = (move_type, i, j)
                if key in self.neighborhood_cache:
                    candidate, candidate_cost = self.neighborhood_cache[key]
                else:
                    candidate = self._apply_operation(sol, move_type, i, j)
                    candidate_cost = get_cost(self.n, self.distmat, candidate)
                    self.neighborhood_cache[key] = (candidate, candidate_cost)
                
                move = self._get_move_fast(sol, candidate)
                is_tabu = move in self.tabu_list
                aspiration = candidate_cost < self.params.get('best_cost', float('inf'))
                
                if not is_tabu or aspiration:
                    candidate_sols.append(candidate)
                    candidate_costs.append(candidate_cost)
            
            if candidate_sols:
                best_idx = np.argmin(candidate_costs)
                chosen_sol = candidate_sols[best_idx]
                chosen_cost = candidate_costs[best_idx]
                move = self._get_move_fast(sol, chosen_sol)
                
                # 添加到禁忌表
                self.tabu_list.append(move)
                
                delta = chosen_cost - cost
                if delta < 0 or random.random() < math.exp(-delta / max(temp, 1e-8)):
                    return chosen_sol, chosen_cost
            return sol, cost
        else:
            return self._sa_step(sol, cost, temp)

    def _get_move_fast(self, old_sol, new_sol):
        """优化的移动识别算法"""
        n = self.n
        diff = []
        for i in range(n):
            if old_sol[i] != new_sol[i]:
                diff.append(i)
                if len(diff) > 2:
                    break
        
        if not diff:
            return ('noop', 0, 0)
        if len(diff) == 2:
            return ('swap', diff[0], diff[1])
        return ('unknown', min(diff), max(diff))

    def _update_tabu_list(self):
        """优化：定期清理禁忌表"""
        # 随机移除一些禁忌项
        if random.random() < 0.1 and self.tabu_list:
            self.tabu_list.popleft()
        
        # 确保禁忌表不超过最大长度
        while len(self.tabu_list) > self.tabu_tenure:
            self.tabu_list.popleft()

    def _sa_vns_step(self, sol, cost, temp, hybrid_ratio=0.7):
        if random.random() < (1 - hybrid_ratio):
            # 优化：使用迭代加深的VND
            new_sol, new_cost = self._vnd_local_search_iterative(sol, cost)
            delta = new_cost - cost
            if delta < 0 or random.random() < math.exp(-delta / max(temp, 1e-8)):
                return new_sol, new_cost
            return sol, cost
        else:
            return self._sa_step(sol, cost, temp)

    def _vnd_local_search_iterative(self, sol, cost):
        """迭代加深的VND局部搜索"""
        current_sol = sol
        current_cost = cost
        improved = True
        depth = 0
        
        while improved and depth < 3:  # 限制最大深度
            improved = False
            neighborhoods = [
                self._swap_neighborhood,
                self._two_opt_neighborhood,
                self._insertion_neighborhood
            ]
            
            # 随机顺序尝试邻域
            random.shuffle(neighborhoods)
            for neighborhood in neighborhoods:
                candidate, candidate_cost = neighborhood(current_sol, current_cost)
                if candidate_cost < current_cost:
                    current_sol = candidate
                    current_cost = candidate_cost
                    improved = True
                    depth = 0  # 重置深度
                    break  # 跳出当前邻域循环
            depth += 1
        
        return current_sol, current_cost

    def _swap_neighborhood(self, sol, cost):
        """优化的交换邻域搜索"""
        n = self.n
        best_sol = sol
        best_cost = cost
        
        # 优化：尝试次数基于问题规模
        attempts = min(max(10, n//10), 50)
        for _ in range(attempts):
            i, j = random.sample(range(n), 2)
            if i == j:
                continue
                
            # 使用缓存操作
            candidate = self._apply_operation(sol, 0, i, j)
            candidate_cost = get_cost(self.n, self.distmat, candidate)
            
            if candidate_cost < best_cost:
                best_sol = candidate
                best_cost = candidate_cost
                # 找到改进后立即返回
                return best_sol, best_cost
        
        return best_sol, best_cost

    def _two_opt_neighborhood(self, sol, cost):
        """优化的2-opt邻域搜索"""
        n = self.n
        best_sol = sol
        best_cost = cost
        
        # 优化：尝试次数基于问题规模
        attempts = min(max(5, n//20), 30)
        for _ in range(attempts):
            if n < 4:
                return sol, cost  # 太小，不适合做2-opt

            i = random.randint(0, n - 3)
            j = random.randint(i + 2, n - 1)

            
            # 使用缓存操作
            candidate = self._apply_operation(sol, 1, i, j)
            candidate_cost = get_cost(self.n, self.distmat, candidate)
            
            if candidate_cost < best_cost:
                best_sol = candidate
                best_cost = candidate_cost
                # 找到改进后立即返回
                return best_sol, best_cost
        
        return best_sol, best_cost

    def _insertion_neighborhood(self, sol, cost):
        """优化的插入邻域搜索"""
        n = self.n
        best_sol = sol
        best_cost = cost
        
        # 优化：尝试次数基于问题规模
        attempts = min(max(10, n//10), 50)
        for _ in range(attempts):
            i = random.randint(0, n-1)
            j = random.randint(0, n-1)
            if abs(i - j) < 2:
                continue
                
            # 使用缓存操作
            candidate = self._apply_operation(sol, 2, i, j)
            candidate_cost = get_cost(self.n, self.distmat, candidate)
            
            if candidate_cost < best_cost:
                best_sol = candidate
                best_cost = candidate_cost
                # 找到改进后立即返回
                return best_sol, best_cost
        
        return best_sol, best_cost

    def strong_perturbation(self, sol):
        """优化的强扰动算法"""
        size = self.n
        if size < 8:
            return sol
            
        # 优化：使用更有效的扰动模式
        pts = sorted(random.sample(range(size), 4))
        a, b, c, d = pts
        
        # 创建新解而不拼接多个列表
        new_sol = sol.copy()
        segment1 = sol[a:b]
        segment2 = sol[b:c]
        segment3 = sol[c:d]
        
        # 重新组合片段
        new_sol[a:a+len(segment3)] = segment3
        new_sol[a+len(segment3):a+len(segment3)+len(segment2)] = segment2
        new_sol[a+len(segment3)+len(segment2):a+len(segment3)+len(segment2)+len(segment1)] = segment1
        
        return new_sol